package leetcode.biweekly.week97;

//Solution4Test
public class Solution5 {
	int m, n;

	public boolean isPossibleToCutPath(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		boolean[][] b = new boolean[m][n];

		if (!f(grid, 0, 0, b)) {
			return true;
		}
		if (f(grid, 0, 0, b)) {
			return false;
		}
		return true;
	}

	private boolean f(int[][] grid, int x, int y, boolean[][] b) {
		if (x == m - 1 && y == n - 1) {
			return true;
		}
		if (b[x][y]) {
			return false;
		}

		if (x != 0 || y != 0) {
			b[x][y] = true;
		}
		if (x + 1 < m && grid[x + 1][y] == 1) {
			if (f(grid, x + 1, y, b)) {
				return true;
			}
		}
		if (y + 1 < n && grid[x][y + 1] == 1) {
			if (f(grid, x, y + 1, b)) {
				return true;
			}
		}
		return false;
	}
}
